"""
杨辉三角
"""
# numRows = 9
# dp=[]
# for i in range(1,numRows+1):
#     dp.append([1]*i)
# for i in range(2,len(dp)):
#     for j in range(1,len(dp[i])-1):
#         dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
# print(dp)
from functools import reduce

from alipay import AliPay, AliPayConfig

"""
字符串翻转
"""
# s = "Let's take LeetCode contest"
# s1=[]
# for i in range(len(s.split())):
#     s1.append(s.split()[i][::-1])
#
# print(' '.join(s1))
"""
二分查找
"""
# nums = [3,4,5,1,2]
# l=0
# h=len(nums)-1
#
# while l<=h:
#     mid=(l+h)//2
#     if nums[l]<=nums[h]:
#         print(nums[l])
#         break
#     elif nums[l]>nums[h]and nums[l]<=nums[mid]:
#         l=mid+1
#     elif nums[l]>nums[h] and nums[mid]<=nums[l]:
#         h=mid
"""
原地删除相同数字
"""
# nums = [0,1,1,2,2]
# slow, fast = 0, 1
#         while fast < len(nums):
#             if nums[fast] != nums[slow]:
#                 slow = slow + 1
#                 nums[slow] = nums[fast]
#             fast = fast + 1
#         return slow + 1
"""
移动0到末尾，相对位置不变
"""
# 1.
# nums = [0,1,0,3,12]
# for i in nums:
#     if i==0:
#         nums.remove(i)
#         nums.append(i)
# print(nums)
# 2.
# n = len(nums)
# left = right = 0 # 初始化左指针和右指针均指向列表的开头
# while right < n:
#     if nums[right] != 0: # 左指针应当指向为0的元素，如果右指针不为0就将左右指针指向的元素互换
#         nums[left],nums[right] = nums[right],nums[left]
#         left += 1
#     right += 1
"""
两个栈实现队列
"""
# class CQueue:
#
#     def __init__(self):
#         self.a,self.b=[],[]
#
#     def appendTail(self, value: int):
#         self.a.append(value)
#
#     def deleteHead(self):
#         if self.b:
#             return self.b.pop()
#         if not self.a:
#             return -1
#         while self.a:
#             self.b.append(self.a.pop())
#         return self.b.pop()
#
#
"""
求各位都不相同的数字个数
"""
# def countNumbersWithUniqueDigits( n):
#     f=[1,9]
#     for i in range(2,n+1):
#         f.append(9-i+2)
#     return f[0]+sum([reduce(lambda x,y: x*y, f[:i+1]) for i in range(1, n+1)])
# print(countNumbersWithUniqueDigits(2))

"""
对一个大小为 n x n 的矩阵而言，如果其每一行和每一列都包含从 1 到 n 的 全部 整数（含 1 和 n），则认为该矩阵是一个 有效 矩阵。
"""
# def checkValid(matrix):
#     f=[]
#     for i in matrix:
#         f.append(set(i))
#     z=list(zip(*matrix))
#     for j in z:
#         f.append(set(j))
#     for i in f:
#         if len(i)<len(matrix):
#             return False
#         else:
#             return True
#
# matrix = [[1, 2, 3], [3, 1, 2], [2, 3, 1]]
# print(checkValid(matrix))

# 接入支付宝
# app_private_key_string = open("alipay_private_key2048.txt").read()
# alipay_public_key_string = open("alipay_public_key2048.txt").read()
#
# alipay = AliPay(
#     # 测试用沙箱appid，上线使用应用的appid
#     appid="2021000119665566",
#     app_notify_url=None,  # 默认回调 url
#     app_private_key_string=app_private_key_string,
#     # 支付宝的公钥，验证支付宝回传消息使用，不是你自己的公钥,
#     alipay_public_key_string=alipay_public_key_string,
#     sign_type="RSA2",  # RSA 或者 RSA2
#     debug=True,  # 默认 False
#     verbose=False,  # 输出调试数据
#     config=AliPayConfig(timeout=60)  # 可选，请求超时时间
# )
# subject = "便利鲜fruitshop商品购买"
#
# # 电脑网站支付，需要跳转到：https://openapi.alipay.com/gateway.do? + order_string
# order_string = alipay.api_alipay_trade_page_pay(
#     out_trade_no="202204132327",  # 输出时间
#     total_amount=0.01,  # 总金额
#     subject=subject,  # 主题
#     return_url=None,
#     notify_url=None  # 可选，不填则使用默认 notify url
# )
#
# # 沙箱网关和应用的不一样
# url = 'https://openapi.alipaydev.com/gateway.do?'
#
# path = url + order_string
# print(path)

"""
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
示例 1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
"""
n = 13
# a=[]
# for i in range(1,n+1):
#     a.append(i)
# a.sort(key=str)
# print(a)
# print(sorted(range(1,n+1), key=str))
# 深度优先搜索树
# res = []
# def dfs(k):
#     if k <= n:
#         res.append(k)
#         t = 10 * k
#         if t <= n:
#             for i in range(10):
#                 dfs(t + i)
#
#
# for i in range(1, 10):
#     dfs(i)
# print(res)

